package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

public class Code1177 {
    public static void main(String[] args) {
        String s = "abcda";
        int[][] queries = {{3, 3, 0}, {1, 2, 0}, {0, 3, 1}};
        System.out.println(new Code1177().canMakePaliQueries(s, queries));
    }

    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        List<Boolean> ans = new ArrayList<>(queries.length);
        char[] chars = s.toCharArray();
        int[] preXor = new int[chars.length + 1];
        for (int i = 0; i < chars.length; i++) {
            preXor[i + 1] = preXor[i] ^ (1 << (chars[i] - 'a'));
        }
        for (int[] query : queries) {
            int left = query[0], right = query[1], k = query[2];
            int xor = preXor[left] ^ preXor[right + 1];
            int bitCount = Integer.bitCount(xor);
            if (((right + 1 - left) & 1) == 1) bitCount--;
            int need = bitCount / 2;
            ans.add(need <= k);
        }
        return ans;
    }
}
